YES(O(1),O(n^3))

We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(n^3)).

Strict Trs:
  { ite(tt(), u, v) -> u
  , ite(ff(), u, v) -> v
  , find(u, v, nil()) -> ff()
  , find(u, v, cons(cons(u, v), E)) -> tt()
  , find(u, v, cons(cons(u2, v2), E)) -> find(u, v, E)
  , complete(u, nil(), E) -> tt()
  , complete(u, cons(v, S), E) ->
    ite(find(u, v, E), complete(u, S, E), ff())
  , clique(nil(), E) -> tt()
  , clique(cons(u, K), E) ->
    ite(complete(u, K, E), clique(K, E), ff()) }
Obligation:
  innermost runtime complexity
Answer:
  YES(O(1),O(n^3))

We use the processor 'Small Polynomial Path Order (PS,3-bounded)'
to orient following rules strictly.

Trs:
  { ite(tt(), u, v) -> u
  , ite(ff(), u, v) -> v
  , find(u, v, nil()) -> ff()
  , find(u, v, cons(cons(u, v), E)) -> tt()
  , find(u, v, cons(cons(u2, v2), E)) -> find(u, v, E)
  , complete(u, nil(), E) -> tt()
  , complete(u, cons(v, S), E) ->
    ite(find(u, v, E), complete(u, S, E), ff())
  , clique(nil(), E) -> tt()
  , clique(cons(u, K), E) ->
    ite(complete(u, K, E), clique(K, E), ff()) }

The induced complexity on above rules (modulo remaining rules) is
YES(?,O(n^3)) . These rules are moved into the corresponding weak
component(s).

Sub-proof:
----------
  The input was oriented with the instance of 'Small Polynomial Path
  Order (PS,3-bounded)' as induced by the safe mapping
  
   safe(ite) = {1, 2, 3}, safe(tt) = {}, safe(ff) = {},
   safe(find) = {1, 2}, safe(nil) = {}, safe(cons) = {1, 2},
   safe(complete) = {1}, safe(clique) = {}
  
  and precedence
  
   complete > ite, complete > find, clique > ite, clique > find,
   clique > complete, ite ~ find .
  
  Following symbols are considered recursive:
  
   {ite, find, complete, clique}
  
  The recursion depth is 3.
  
  For your convenience, here are the satisfied ordering constraints:
  
                         ite(; tt(),  u,  v) > u                                                
                                                                                                
                         ite(; ff(),  u,  v) > v                                                
                                                                                                
                          find(nil(); u,  v) > ff()                                             
                                                                                                
      find(cons(; cons(; u,  v),  E); u,  v) > tt()                                             
                                                                                                
    find(cons(; cons(; u2,  v2),  E); u,  v) > find(E; u,  v)                                   
                                                                                                
                      complete(nil(),  E; u) > tt()                                             
                                                                                                
              complete(cons(; v,  S),  E; u) > ite(; find(E; u,  v),  complete(S,  E; u),  ff())
                                                                                                
                          clique(nil(),  E;) > tt()                                             
                                                                                                
                  clique(cons(; u,  K),  E;) > ite(; complete(K,  E; u),  clique(K,  E;),  ff())
                                                                                                

We return to the main proof.

We are left with following problem, upon which TcT provides the
certificate YES(O(1),O(1)).

Weak Trs:
  { ite(tt(), u, v) -> u
  , ite(ff(), u, v) -> v
  , find(u, v, nil()) -> ff()
  , find(u, v, cons(cons(u, v), E)) -> tt()
  , find(u, v, cons(cons(u2, v2), E)) -> find(u, v, E)
  , complete(u, nil(), E) -> tt()
  , complete(u, cons(v, S), E) ->
    ite(find(u, v, E), complete(u, S, E), ff())
  , clique(nil(), E) -> tt()
  , clique(cons(u, K), E) ->
    ite(complete(u, K, E), clique(K, E), ff()) }
Obligation:
  innermost runtime complexity
Answer:
  YES(O(1),O(1))

Empty rules are trivially bounded

Hurray, we answered YES(O(1),O(n^3))